This invention relates to an improved method and apparatus for incremental computation of a linear function.
A known digital plotter has a print head which is used to apply a print medium, such as ink, to a record medium, such as paper. The record medium is held stationary relative to a support frame. The print head is mounted on a carriage which is movable along a guide structure in directions along a first axis under control of a first motor. The guide structure is movable relative to the support frame in directions parallel to a second axis (which is perpendicular to the first axis) under control of a second motor. The print head is able to apply print medium to the record medium only at discrete, equally-spaced locations along the first and second axes. The locations to which print medium may be applied thus form a square mesh. As shown in FIG. 1, in which the first and second axes are designated X and Y, the print head may be moved from a starting position, in which it is able to apply a dot to a mesh point 2 having coordinates (O,O), in any one of eight directions such that it arrives at a new position in which it is able to apply a dot to a mesh point 4 having coordinates (X1,Y1) where either X1 or Y1 has an absolute value of 1 and the other coordinate is -1, 0 or +1. Such a plotter is referred to hereinafter as a plotter of the aforesaid kind. In a plotter of the aforesaid kind, the movement of the print head along one axis is independent of its movement along the other axis.
A plotter of the aforesaid kind may be used to simulate a straight line at an arbitrary orientation by applying dots of print medium to the record medium at appropriately selected mesh points. Each two adjacent dots form a line segment, and in general the straight line is simulated by writing a succession of line segments in which each line segment is either parallel to a selected one of the first and second axes or is parallel to a selected diagonal to the first and second axes. As shown in FIG. 1, the line 10 from the point 2 to the point 16 having coordinates (Dx, Dy) is created by writing line segments A that are parallel to the X axis and line segments B that are parallel to the diagonal at +45.degree. to the positive X direction. No other line segments are needed to simulate the straight line.
When a plotter of the aforesaid kind is used in this manner to simulate a line, it is necessary to be able to determine rapidly whether the next line segment should be along one of the first and second axes or diagonal to the first and second axes. FIG. 1 shows that a better simulation of the line 10 is provided by selecting the path 12, indicated by single arrows, than by selecting the path 14, indicated by double arrows.
J. E. Bresenham, Algorithm for Computer Control of a Digital Plotter, IBM Systems Journal, Vol. 4, 25 (1965), describes an algorithm which enables a plotter of the aforesaid kind to select a path that provides a good simulation of a straight line without its being necessary to carry out a multiplication or division operation.
Using the teaching of Bresenham, but with different notation, we can consider the case of representing the line drawn from (O,O) to (Dx,Dy) in FIG. 1. Bresenham's algorithm solves the case for the first octant, where Dx&gt;=Dy&gt;=0 and Dx&gt;0. A line in the first octant is simulated by writing line segments along the X axis (0.degree. in polar coordinates) and line segments along the diagonal at +45.degree.. The algorithm minimizes the vertical error between the line and the points chosen to represent it. The equation of the line that is to be approximated is Yt=(Dy/Dx)*X. Yt, the "true" value of Y, is a function of X which we write explicitly as: EQU Yt(X)=(Dy/Dx)*X
For integer values of X, the algorithm chooses an integer value Ya to approximate Yt. The vertical error in this approximation is Ev(X)=Ya(X)-Yt(X). Because Ya is restricted to be an integer, we see that the optimal value of Ya obeys the condition abs[Ev(X)]&lt;=1/2. If Yt(X)=n+(1/2) for some integer n, then there are two equally optimal approximations, namely Ya(X)=n and Ya(X)=n+1. To create a unique value of Ya for all X, we make the more restrictive requirement that one of the following two inequalities must hold: ##EQU1## Bresenham's algorithm obeys [1.1A].
The algorithm involves an incremental calculation along the X axis. Therefore given Ya(X), Ev(X), Dx and Dy, we want to calculate Ya(X+1). To facilitate further generalizations, let us define EQU X'=X+1 [1.2]
We have from the definition of Ev, the relation ##EQU2## From [1.3] we have EQU Ev(X')=Ev(X)-(Dy/Dx)+[Ya(X')-Ya(X)].
Applying [1.1A] to this equation gives EQU -(1/2))&lt;Ev(X)-(Dy/Dx)+[Ya(X')-Ya(X)]&lt;=+(1/2),
which produces the two relationships EQU Ya(X')-Ya(X)&gt;-Ev(X)+(Dy/Dx) -(1/2) [1.4A] EQU Ya(X')-Ya(X)&lt;=-Ev(X)+(Dy/Dx)+(1/2) [1.4B]
Using the inequalities (Dy/Dx)&gt;=0 and -Ev(X)&gt;=-(1/2) in [1.4A] gives EQU Ya(X')-Ya(X)&gt;-(1.2)+0-(1/2) EQU Ya(X')-Ya(X)&gt;-1. [1.5]
Using the inequalities (Dy/Dx)&lt;=1 and -Ev(X)&lt;(1/2) in [1.4B] gives EQU Ya(X')-Ya(X)&lt;(1/2)+1+1(1/2), EQU Ya(X')-Ya(X)&lt;2. [1.6]
Since Ya(X) and Ya(X') are integers, one of the following two conditions must be true: ##EQU3## [1.7A] represents a horizontal juxtaposition of the pixels (X,Y(X)) and (X',Y(X')) while [1.7B] represents a diagonal juxtaposition of these pixels. We call [1.7A] a Horizontal Draw and [1.7B] a Diagonal Draw.
If we have the condition EQU -Ev(X)+(Dy/Dx)-(1/2)&gt;=0 [1.8]
then from [1.4A] we see that Ya(X')-Ya(X)&gt;0. From this it follows that [1.7A] cannot hold so that [1.7B] must be true, that is Ya(X')=Ya(X)+1. If we have the condition EQU -Ev(X)+(Dy/Dx)+(1/2)&gt;1 [1.9]
then from [1.4B] we see that Ya(X')-Ya(X)&lt;1. From this it follows that [1.7B] cannot hold so that [1.7A] must be true, that is Ya(X')=Ya(X). Let us define EQU Er(X)=-Ev(X)+(Dy/Dx)-(178 ). [1.10]
We have determined that the following rule holds: ##EQU4## Since these two conditions exhaust the possible values of Er(X), this rule completely determines the algorithm. To initialize the algorithm, we easily see that the optimal value of Ya(0) is 0 so that Ev(0)=0 and Er(0)=-0+(Dy/Dx)-(1/2). From [1.3], we see that ##EQU5## Thus if a Diagonal Draw is performed, then EQU Er(X')=Er(X)+(Dy/Dx)-1
and if a Horizontal Draw is performed, then EQU Er(X')=Er(X)+(Dy/Dx).
For the first octant, then, the Bresenham algorithm can be written as
______________________________________ Er := (Dy/Dx) - 0.5; [Algorithm 1.1] For i := 1 to Dx do If Er &gt;=0 then Er := Er + (Dy/Dx) - 1; Diagonal Draw; Else {Er &lt; 0} Er := Er + (Dy/Dx); Horizontal Draw; End-If; End-for; ______________________________________
Multiplying by 2*Dx gives the equivalent integer algorithm
______________________________________ Er := 2*Dy -Dx; {Algorithm 1.2} For i := 1 to Dx do If Er &gt;=0 then Er := Er + 2*Dy - 2*Dx; Diagonal Draw; Else {Er &lt; 0} Er := Er + 2*Dy; Horizontal Draw; End-If; End-for; ______________________________________
Bresenham's algorithm is restricted to the case in which the line to be simulated is in the first octant. In order to simulate a line that lies in one of the other octants it is necessary to change signs and/or exchange the X and Y axes in the algorithm. When the X and Y axes are exchanged, the vertical error Ev becomes the horizontal error. For all Y (0&lt;=Y &lt;=Dy) where Dy&gt;0, the algorithm chooses an approximation Xa(Y) to the "true" line Xt(Y) =(Dx/Dy)*Y. X is then considered to be a function of Y, and it is necessary to carry out one iteration of the algorithm for each value of Y. This can be tolerated in the case of a plotter of the aforesaid kind, precisely because movement of the print head along the second axis is independent of its movement along the first axis.
In a digitally-addressed raster scan CRT, such as might be employed in a computer-aided design (CAD) system, an image is created by selectively illuminating a rectangular array of pixels, adjacent pixels in a horizontal line being addressed consecutively and being illuminated in accordance with a Z-axis control signal. If it is desired to illuminate a first pixel which lies on a first raster line and a second pixel which lies on an adjacent raster line and is either vertically aligned with the first pixel or is adjacent to the first pixel with respect to the horizontal direction, it is necessary to address up to an entire line of pixels between illuminating the first pixel and illuminating the second pixel. If Bresenham's algorithm is used to determine whether a pixel is to be illuminated, and the determination is made concurrently with the creation of the image on the CRT screen, it takes longer to simulate a line that is at less than 45 degrees to the vertical axis than to simulate a line of the same length that is at less than 45 degrees to the horizontal axis.
A CAD system may be used to provide a two-dimensional display of a three-dimensional object. In a simple case, as shown in FIG. 2, the object may have planar surfaces 20 and 22 which are defined between vertical lines 24, 26 and 28. If it is desired to display the object in an orientation such that the line 26 appears closer to the viewer than the line 24 and the line 28 appears closer than the line 26, increased realism may be provided by shading so that the brightness with which the surfaces 20 and 22 are shown increases from left to right of the CRT screen. This is accomplished by increasing the beam current of the CRT in accordance with a known function, e.g. a linear function, as the beam sweeps from left to right between each two vertical lines. In order to provide "real time" presentation of moving three-dimensional objects, it is necessary to calculate the intensity with which each pixel will be illuminated "on the fly". That is, the calculation of the intensity to use for the next adjacent pixel is done at the same time as the current pixel is being illuminated. For example, if the calculation for pixel 30 (FIG. 3) has been completed and pixel 30 is illuminated at the required intensity on field N, the calculation for the adjacent pixel 32 is then carried out and pixel 32 is illuminated at the required intensity on field N+n. In this manner, the surfaces 20 and 22 are filled progressively.
It is desirable that the minimum beam current and the maximum beam current be adjustable independently of each other and that the horizontal distance between each two vertical lines be adjustable. If the beam current is digitally controlled and has, for example, 256 discrete levels between the levels selected for the left and right edges of the surfaces and the CRT has 1024 pixels between the lines 24 and 26 and between the lines 26 and 28, the rate of increase of the beam current from left to right is less than one step per pixel. Several pixels in a given raster line may be illuminated at the same intensity, followed by an increase of one step and then several more pixels may be illuminated at the same, increased intensity. In this case, n might be equal to 1. However, in a practical CAD system there may be as many as 65,536 discrete beam current levels between the level selected for the left edge of the surface 20 or 22 and the level selected for the right edge of the surface, so that adjacent pixels on a given line might be addressed at currents that differ from each other by multiple steps. Under these circumstances, using Bresenham's algorithm to calculate the number of steps by which the current must increase from the pixel 30 to the pixel 32 takes much longer because one iteration of the algorithm is required for each current level and n may be substantially greater than 1. If there are fewer than 1024 discrete current levels between the levels selected for the lines 24 and 26 and more than 1024 levels between the levels selected for the lines 26 and 28, it will take longer to fill the area 22 than the area 20. This difference in the rate of fill of different surfaces may be disturbing to the user of the CAD system.
Many CAD systems utilize dedicated microprocessors to carry out the calculations that are required in order to determine which pixels must be illuminated and at what intensity, because microprocessors run more rapidly than other processors and therefore are potentially able to complete the calculations more quickly than other processors. A disadvantage of microprocessors is that they have relatively unsophisticated instruction sets, and are not able to carry out such complex operations as a processor with a more extensive instruction set. Bresenham's algorithm is in principle well suited to use with microprocessor-based CAD systems because it does not require repeated multiplication or division operations. However, the above-described disadvantage of Bresenham's algorithm has previously prevented widespread use of the algorithm in microprocessor-based CAD systems for providing a two-dimensional display of a three-dimensional object.